package com.tim.ying.tree.huffman;

import java.util.Arrays;

import com.tim.ying.tree.node.TreeNode;

/**
 * 哈夫曼树
 * 又称最优二叉树
 * 假设有n个权值{w1,w2....wn},如果构造一棵有n个叶子节点的二叉树，而这n个叶子节点的权值是{w1,w2,...,wn}，则所构造出的带权路径长度最小的二叉树就被称为赫夫曼树
 * 带权路径长:树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和，如果在一棵二叉树中共有n个叶子节点，用Wi表示第i个叶子节点的权值，Li表示第i个也叶子节点到根节点的路径长度，则该二叉树的带权路径长度 WPL=W1*L1 + W2*L2 + ... Wn*Ln
 * 
 *  根据节点的个数以及权值的不同，赫夫曼树的形状也各不相同，赫夫曼树具有如下特性：
 *	1,对于同一组权值，所能得到的赫夫曼树不一定是唯一的。
 *	2,赫夫曼树的左右子树可以互换，因为这并不影响树的带权路径长度。
 *	3,带权值的节点都是叶子节点，不带权值的节点都是某棵子二叉树的根节点。
 *	4,权值越大的节点越靠近赫夫曼树的根节点，权值越小的节点越远离赫夫曼树的根节点。
 *	5,赫夫曼树中只有叶子节点和度为2的节点，没有度为1的节点。
 *	6,一棵有n个叶子节点的赫夫曼树共有2n-1个节点。
 * @author yingbibo
 * 
 * 按二叉树规则 左小右大 组合
 *
 */
public class HuffmanTree {       
	/**
	 * 哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
	 * 输入有多组数据。
	 * 每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
	 * @param args
	 */
	
	public static void main(String[] args) {
		//int[] weights = new int[]{1,2,2,5,9};
		//int[] weights = new int[]{1,2,3,7};

		int[] weights = new int[]{5,29,7,8,14,23,3,11};
		TreeNode[] nodes = new TreeNode[weights.length];
		for(int i=0;i<weights.length;i++){
			TreeNode node = new TreeNode(null, weights[i]);
			nodes[i] = node;
		}
		TreeNode treeNode = buildTree(nodes);
		System.out.println(list(treeNode, 0));
		
		
	}
	
	private static TreeNode buildTree(TreeNode[] weights){
		Arrays.sort(weights, (TreeNode node1,TreeNode node2)->{
			if(node1.weight==node2.weight){
				if(node1.left!=null){
					return -1;
				}
			}
			return node1.weight-node2.weight;
		}
				);
		if(weights.length==1){
			return weights[0];
		}else{
			TreeNode leftNode = weights[0];
			TreeNode rightNode = weights[1];
			TreeNode preNode = new TreeNode(null, leftNode.weight+rightNode.weight);
			preNode.left = leftNode;
			preNode.right = rightNode;
			TreeNode[] newWeights = new TreeNode[weights.length-1];
			System.arraycopy(weights, 2, newWeights, 0, weights.length-2);
			newWeights[newWeights.length-1]=preNode;
			return buildTree(newWeights);
		}
	}
	
	
	public static int list(TreeNode treeNode,int level){
		if(treeNode==null){
			return 0;
		}else{
			int left = list(treeNode.left, level+1);
			int right = list(treeNode.right, level+1);
			int i = treeNode.left==null?treeNode.weight*level:0;
			return i+left+right;
		}
	}
}
